#!/usr/bin/python
#
# exp.py - Classes to represent underlying data structures for the grammar
#     below, for the mini-compiler.
#
# Kurt Schmidt
# 8/07
#
# DESCRIPTION:
#        Just a translation of the C++ implementation by Jeremy Johnson (see
#        programext.cpp)
#
# EDITOR: cols=80, tabstop=2
#
# NOTES
#    environment:
#        a dict
#
#        Procedure calls get their own environment, can not modify enclosing env
#
#    Grammar:
#        program: stmt_list 
#        stmt_list:  stmt ';' stmt_list 
#            |   stmt  
#        stmt:  assign_stmt 
#            |  define_stmt 
#            |  if_stmt 
#            |  while_stmt 
#        assign_stmt: IDENT ASSIGNOP expr
#        define_stmt: DEFINE IDENT PROC '(' param_list ')' stmt_list END
#        if_stmt: IF expr THEN stmt_list ELSE stmt_list FI
#        while_stmt: WHILE expr DO stmt_list OD
#        param_list: IDENT ',' param_list 
#            |      IDENT 
#        expr: expr '+' term   
#            | expr '-' term   
#            | term            
#        term: term '*' factor   
#            | factor            
#        factor:     '(' expr ')'  
#            |       NUMBER 
#            |       IDENT 
#            |       funcall 
#        funcall:  IDENT '(' expr_list ')'
#        expr_list: expr ',' expr_list 
#            |      expr 
#

import sys

####  CONSTANTS   ################

    # the variable name used to store a proc's return value
returnSymbol = 'return'

tabstop = '  ' # 2 spaces

######   CLASSES   ##################

class Expr :
	'''Virtual base class for expressions in the language'''

	def __init__( self ) :
		raise NotImplementedError('Expr: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft, ht ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''
		raise NotImplementedError('Expr.eval: virtual method.  Must be overridden.' )

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
		'Expr.display: virtual method.  Must be overridden.' )



class NameTableEntry:

	def __init__(self, element, isList):
		self.element = element
		self.isList = isList

	def eval(self, nt,ft,ht) :
		return self

class HeapCell:

	def __init__(self,car,cdr,isPtr):
		self.car = car
		self.cdr = cdr
		self.isPtr = isPtr
		self.mark = 0

class Heap :
	memTracker = []
	lastIndexUsed = 0
	def __init__(self):
		self.array = [None]*15
		for i  in range(0,len(self.array)):
			self.array[i] = HeapCell(0,i+1,0)
		self.array[len(self.array)-1].cdr = -1
                self.available = 0

	def add_to_list(self, car,cdr, isPtr, nt) :
		if(self.available == -1):
			self.mark_and_sweep(nt)
		if(self.available == -1):
			print "Full Memory"
			sys.exit(0)

#		print "here"
		# if(cdr.element == -1):
		#  print "neg1"      


		index = self.available #set available to index for indertion
		self.available = self.array[self.available].cdr #update available
		# print car
		# print str(cdr)
		#self.array[index].car = car.element
		if(cdr.element  == -1):
			self.array[index].cdr = -1
			self.array[index].car = car
		else:
			self.array[index].cdr = cdr.element
			self.array[index].car = car

#		print str(car)
		if type(self.array[index].car) is not int:
			self.array[index].car = self.memTracker.pop()
		self.array[index].mark = 1
		self.array[index].isPtr = isPtr
#		self.array[index] = HeapCell(car, cdr,isPtr)

		self.lastIndexUsed = index
#		print "Available"
#		print self.available
		return NameTableEntry(index,1)        
		#return index

	def isList(self, addr):
		if(self.array[addr].isPtr == 1):
			return 1
		else:
			return 0
	def mark(self, addr) :
#		print "Addr" + str(addr)
		if(addr != -1):
			print "Marked" + str(addr) #for testing purposes
			self.array[addr].mark = 1 #mark it
			self.mark(self.array[addr].cdr) #mark its reference
			if(self.array[addr].isPtr == 1): #if its a list
				self.mark(self.array[addr].car)

	def sweep(self, addr) :
		self.array[addr].car = 0
		self.array[addr].cdr = self.available
		self.array[addr].isPtr = 0
		self.available = addr

	def mark_and_sweep(self, nt):
		for n in nt :
			if(nt[n].isList == 1):
				#print nt[n].element
				self.mark(nt[n].element)

		for m in range(len(self.array)):
			if(self.array[m].mark == 0):
				print "reclaimed" + str(m)
				self.sweep(m)
			else:
				self.array[m].mark = 0

	def printHeap(self) :
		for i in range(0, len(self.array)) :
			index = str(i)
			car = str(self.array[i].car)
			cdr = str(self.array[i].cdr)
			isPtr = str(self.array[i].isPtr)
			mark = str(self.array[i].mark)
			if self.isList(i) :
				car = str(self.array[i].car)
			print "index -> %s car -> %s cdr -> %s isPtr -> %s mark -> %s" % (index, car, cdr, isPtr, mark)


class Number( Expr ) :
	'''Just integers'''

	def __init__( self, v=0 ) :
		self.value = v
		self.isList = 0
	def eval( self, nt, ft, ht ) :
		return self.value

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)

class Ident( Expr ) :
	'''Stores the symbol'''

	def __init__( self, name ) :
		self.name = name
	def eval( self, nt, ft, ht ) :
		return nt[ self.name ]

	def display( self, nt, ft, depth=0 ) :
		print "%s%s" % (tabstop*depth, self.name)


class Times( Expr ) :
	'''expression for binary multiplication'''

	def __init__( self, lhs, rhs ) :
		'''lhs, rhs are Expr's, the operands'''

		# test type here?
		# if type( lhs ) == type( Expr ) :
		self.lhs = lhs
		self.rhs = rhs
		self.isList = 0

	def eval( self, nt, ft, ht ) :
		return self.lhs.eval( nt, ft, ht ) * self.rhs.eval( nt, ft, ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sMULT" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Plus( Expr ) :
	'''expression for binary addition'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
	def eval( self, nt, ft, ht ) :
		return self.lhs.eval( nt, ft, ht ) + self.rhs.eval( nt, ft, ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sADD" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Minus( Expr ) :
	'''expression for binary subtraction'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
		self.isList = 0

	def eval( self, nt, ft, ht ) :
		return self.lhs.eval( nt, ft, ht ) - self.rhs.eval( nt, ft, ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sSUB" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class FunCall( Expr ) :
	'''stores a function call:
	- its name, and arguments'''

	def __init__( self, name, argList ) :
		self.name = name
		self.argList = argList
		self.isList = 0

	def eval( self, nt, ft, ht ) :
		return ft[ self.name ].apply( nt, ft, self.argList )

	def display( self, nt, ft, depth=0 ) :
		print "%sFunction Call: %s, args:" % (tabstop*depth, self.name)
		for e in self.argList :
			e.display( nt, ft, depth+1 )


class Cons( Expr ) :
	'''puts element at beginning of list'''
	def __init__( self, listelement, list):
		self.listelement = listelement
		self.list = list
	def eval(self, nt, ft, ht):
		#self.listelement = self.listelement.eval(nt,ft, ht)
		#self.list = self.list.eval(nt,ft, ht)
		#if(type(self.list) is int):
		#    sys.exit("Cons second argument must be of type list")
		#c = []
		#for i in range(0,len(self.list)):
		#    c.append(self.list[i])
		#c.insert(0,self.listelement)
		#return c
		return ht.add_to_list(self.listelement.eval(nt,ft,ht), self.list.eval(nt,ft,ht), self.listelement.isList, nt)


class Car( Expr ) :
	'''Removes first element in the list'''
	def __init__(self, list):
		self.list = list
		self.isList = 0     

	def eval(self, nt, ft, ht) :
		rList = self.list.eval(nt,ft, ht)
#		if(type(rList) is int):
#			sys.exit("Car argument must be of type list")
#		if(len(rList) < 1):
#			sys.exit("Car argument must be a non-null list")
#		return rList[0]
		if(ht.array[rList.element].isPtr == 1):
			c = []
			nextIndex = ht.array[rList.element].car
			print nextIndex
			newIndex = 0
			while (nextIndex != -1):
				c.insert(newIndex, ht.array[nextIndex].car)
				nextIndex = ht.array[nextIndex].cdr
				newIndex = newIndex + 1
			return NameTableEntry(c,1)
		else:
			return NameTableEntry(ht.array[rList.element].car,1)
class Cdr ( Expr ) :
	'''Returns all but first element'''
	def __init__(self, list):
		self.list = list
	def eval(self, nt, ft, ht) :
		rList = self.list.eval(nt,ft, ht)
		nextIndex = ht.array[rList.element].cdr
		c = []
		newIndex = 0
		while (nextIndex != -1):
			if(ht.array[nextIndex].isPtr == 1):
				subNextIndex = ht.array[nextIndex].car
				subIndex = 0
				d = []
				while(subNextIndex != -1):
					d.insert(subIndex, ht.array[subNextIndex].car)
					subNextIndex = ht.array[subNextIndex].cdr
					subIndex = subIndex + 1
				c.insert(newIndex, d)
			else:
				c.insert(newIndex, ht.array[nextIndex].car)
			nextIndex = ht.array[nextIndex].cdr
			newIndex = newIndex + 1
#		if(type(rList) is int):
#			sys.exit("Cdr argument must be of type list")
#		c = []
#		for i in range(1,len(rList)):
#			c.append(rList[i])
		return NameTableEntry(c,1)

class Nullp ( Expr ) :
	'''Returns 1 if L is null, 0 otherwise'''
	def __init__(self, list):
		self.list = list
	def eval(self, nt, ft, ht) :
		rList = self.list.eval(nt,ft, ht)
#		if(type(rList) is int):
#			sys.exit("Nullp argument must be of type list")
#		if(len(rList)==0) :
#			return 1
#		else :
#			return 0
		if(rList.element == -1):
			return NameTableEntry(1,1)
		else :
			return NameTableEntry(0,1)
class Intp ( Expr ) :
	'''Returns 1 if E is an integer, 0 otherwise'''
	def __init__(self, e) :
		self.e = e
	def eval(self, nt, ft, ht) :
		rE = self.e.eval(nt,ft,ht)
		if(type(rE) is int):
			return NameTableEntry(1,1)
		else :
			return NameTableEntry(0,1)

class Listp ( Expr ) :
	'''Returns 1 if E is a list, 0 otherwise'''
	def __init__(self, e) :
		self.e = e
	def eval(self, nt, ft, ht) :
		rE = self.e.eval(nt,ft, ht)
		if(type(rE) is int):
			return NameTableEntry(0,1)
		else :
			return NameTableEntry(1,1)
class Concat ( Expr ) :
	'''Concatenates two lists'''
	def __init__(self, l1, l2):
		self.l1 = l1
		self.l2 = l2
	def eval(self, nt, ft, ht) :
		rL1 = self.l1.eval(nt,ft, ht)
		rL2 = self.l2.eval(nt,ft, ht)
		if(type(rL1) is int or type(rL2) is int):
			sys.exit("List concatenation requires two lists")
		c = []
		for i in range(0,len(rL1)) :
			c.append(rL1[i])
		for i in range(0,len(rL2)) :
			c.append(rL2[i])
		return c


class List( Expr ) :
	'''List'''
	def __init__(self, seq=[]) :
		self.seq = seq
		self.isList = 1
	def insert(self, listelement) :
		self.seq.insert(listelement, self.seq)      

	def eval(self, nt, ft, ht) :
		return self.seq.eval(nt,ft, ht)


	def display( self, nt, ft, depth=0):
		print "%sList[" % (tabstop*depth)
		self.seq.display(nt,ft,depth+1)
		print "%s]" % (tabstop*depth)
	def size(self) :
		return len(self.seq)

class Sequence ( Expr ) :
	'''Sequence'''
	def __init__(self):
		self.seq = NameTableEntry(-1,1)
		self.isList = 1
		self.listelement = 0
	def insert(self, listelement):
		self.seq = Cons(listelement, self.seq)  
	def eval(self, nt, ft, ht) :
		#seqValue = []
		#for s in self.seq :
		#    seqValue.append(s.eval(nt,ft,ht))
		#return seqValue
		return self.seq.eval(nt, ft, ht)
	def display(self, nt, ft, depth=0):
		print "%sSeqence " % (tabstop*depth)
		for s in self.seq :
			s.display(nt,ft,depth+1)
	def size(self) :
		return len(self.seq)

class Listelement( Expr ) :
	'''List Element'''
	def __init__(self, element) :
		self.element = element
		self.isList = element.isList
	def eval(self, nt, ft, ht) :

		returnElement = self.element.eval(nt,ft,ht)
		if self.isList:
			ht.memTracker.append(ht.lastIndexUsed)
		return returnElement
	def display(self, nt,ft, depth=0):
		print "%s" % (tabstop*depth)
		self.element.display(nt,ft,depth+1)


#-------------------------------------------------------

class Stmt :
	'''Virtual base class for statements in the language'''
	def __init__( self ) :
		raise NotImplementedError(
		'Stmt: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft, ht ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''
		raise NotImplementedError(
		'Stmt.eval: virtual method.  Must be overridden.' )

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
		'Stmt.display: virtual method.  Must be overridden.' )


class AssignStmt( Stmt ) :
	'''adds/modifies symbol in the current context'''

	def __init__( self, name, rhs ) :
		'''stores the symbol for the l-val, and the expressions which is the
		rhs'''
		self.name = name
		self.rhs = rhs

	def eval( self, nt, ft, ht ) :
		nt[ self.name ] = self.rhs.eval( nt, ft,ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sAssign: %s :=" % (tabstop*depth, self.name)
		self.rhs.display( nt, ft, depth+1 )


class DefineStmt( Stmt ) :
	'''Binds a proc object to a name'''

	def __init__( self, name, proc ) :
		self.name = name
		self.proc = proc

	def eval( self, nt, ft, ht ) :
		ft[ self.name ] = self.proc

	def display( self, nt, ft, depth=0 ) :
		print "%sDEFINE %s :" % (tabstop*depth, self.name)
		self.proc.display( nt, ft, depth+1 )


class IfStmt( Stmt ) :

	def __init__( self, cond, tBody, fBody ) :
		'''expects:
		cond - expression (integer)
		tBody - StmtList
		fBody - StmtList'''

		self.cond = cond
		self.tBody = tBody
		self.fBody = fBody

	def eval( self, nt, ft, ht ) :
		if self.cond.eval( nt, ft ) > 0 :
			self.tBody.eval( nt, ft )
		else :
			self.fBody.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sIF" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sTHEN" % (tabstop*depth)
		self.tBody.display( nt, ft, depth+1 )
		print "%sELSE" % (tabstop*depth)
		self.fBody.display( nt, ft, depth+1 )


class WhileStmt( Stmt ) :

	def __init__( self, cond, body ) :
		self.cond = cond
		self.body = body

	def eval( self, nt, ft, ht ) :
		while self.cond.eval( nt, ft ) > 0 :
			self.body.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sWHILE" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sDO" % (tabstop*depth)
		self.body.display( nt, ft, depth+1 )

class WhileNotStmt( Stmt ) :

	def __init__( self, cond, body ) :
		self.cond = cond
		self.body = body

	def eval( self, nt, ft, ht) :
		while self.cond.eval( nt, ft ) < 1:
			self.body.eval(nt, ft)

	def display( self, nt, ft, depth=0) :
		print "%sWHILE NOT" % (tabstop*depth)
		self.cond.display(nt,ft,depth+1)
		print "%sDO" % (tabstop*depth)
		self.body.display(nt,ft,depth+1)

#-------------------------------------------------------

class StmtList :
	'''builds/stores a list of Stmts'''

	def __init__( self ) :
		self.sl = []

	def insert( self, stmt ) :
		self.sl.insert( 0, stmt )

	def eval( self, nt, ft, ht ) :
		for s in self.sl :
			s.eval( nt, ft, ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sSTMT LIST" % (tabstop*depth)
		for s in self.sl :
			s.display( nt, ft, depth+1 )


class Proc :
	'''stores a procedure (formal params, and the body)

    Note that, while each function gets its own environment, we decided not to
    allow side-effects, so, no access to any outer contexts.  Thus, nesting
    functions is legal, but no different than defining them all in the global
    environment.  Further, all calls are handled the same way, regardless of
    the calling environment (after the actual args are evaluated); the proc
    doesn't need/want/get an outside environment.'''

	def __init__( self, paramList, body ) :
		'''expects a list of formal parameters (variables, as strings), and a
        StmtList'''

		self.parList = paramList
		self.body = body

	def apply( self, nt, ft, args ) :
		newContext = {}

	# sanity check, # of args
		if len( args ) is not len( self.parList ) :
			print "Param count does not match:"
			sys.exit( 1 )

	# bind parameters in new name table (the only things there right now)
# use zip, bastard
		for i in range( len( args )) :
			newContext[ self.parList[i] ] = args[i].eval( nt, ft )

		# evaluate the function body using the new name table and the old (only)
		# function table.  Note that the proc's return value is stored as
		# 'return in its nametable

		self.body.eval( newContext, ft )
		if newContext.has_key( returnSymbol ) :
			return newContext[ returnSymbol ]
		else :
			print "Error:  no return value"
			sys.exit( 2 )

	def display( self, nt, ft, depth=0 ) :
		print "%sPROC %s :" % (tabstop*depth, str(self.parList))
		self.body.display( nt, ft, depth+1 )


class Program :

	def __init__( self, stmtList ) :
		self.stmtList = stmtList
		self.nameTable = {}
		self.funcTable = {}
		self.heapTable = Heap()

	def eval( self ) :
		self.stmtList.eval( self.nameTable, self.funcTable, self.heapTable )

	def dump( self ) :
		print "Dump of Symbol Table"
		print "Name Table"
		for k in self.nameTable :
		#	if type(self.nameTable[k].element) is not int:
		#		print " %s -> %s " % ( str(k),str(self.heapTable.array[self.nameTable[k].element[0]]))
		#		go = true
		#		while(go is true):
		#			self.heapTable.array[self.nameTable[k].element[0]].car
		#	else:
			print "  %s -> %s " % ( str(k), str(self.nameTable[k].element) )

		print "Heap"
		self.heapTable.printHeap()
		print "Function Table"
		for k in self.funcTable :
			print "  %s" % str(k)

	def display( self, depth=0 ) :
		print "%sPROGRAM :" % (tabstop*depth)
		self.stmtList.display( self.nameTable, self.funcTable )


